package com.berchen.数据结构.单链表;

/**
 * 环形单链表 约瑟夫问题
 * 10个人围坐一圈 然后从n开始  报数报到k的时候这个人就出局 然后继续 求出输入的顺序
 * 找到报数的位置 移动k-1次
 * 找到要出圈的人 移动n-1次
 *
 */
public class RingsSingleLinketList {
    private Node first;
    private Node end;

    public RingsSingleLinketList() {
    }
    public int getCount(){
        if(isEmpty()) return 0;
        Node temp=first;
        int count=1;
        while (temp.next!=first){
            count++;
            temp=temp.next;
        }
        return count;
    }

    public boolean isEmpty() {
        return first == null;
    }

    /**
     * 约瑟夫的出圈的问题
     * @param k 从first开始数 第几个人开始数
     * @param m 报数多少个数
     */
    public void chuQuan(int k,int m){

        if(isEmpty()) {
            System.out.println("链表为null");
            return;
        }
        if(k>getCount()||k<=0||m<=0){
            throw new RuntimeException("k值不符合或");
        }

        // 移动k-1次  到开始报数的位置
        for(int i =0;i<k-1;i++){
            first=first.next;
            end=end.next;
        }
        // 开始出圈  直到圈中只有一个人
        while (true){
            if(end==first){
                break;
            }
            // 开始报数
            for(int i =0;i<m-1;i++){
                first=first.next;
                end=end.next;
            }
            // 出圈
            System.out.println(first);
            end.next=first.next;
            first=first.next;
        }
        System.out.println(first);

    }
    /**
     * 批量添加数据
     *
     * @param num
     */
    public void add(int num) {

        if (num <= 0) return;
        for (int i = 1; i <= num; i++) {
            Node node = new Node(i, i + "", i + "");
            if (isEmpty()) {
                first = node;
                first.next=first;
                end = node;
            } else {
                end.next = node;
                node.next = first;
                end = node;
            }
        }
    }

    /**
     * 遍历该链表
     */
    public void list() {
        if (isEmpty()) {
            System.out.println("链表为空");
            return;
        }
        Node temp=first;
        while (temp.next!=first){
            System.out.println(temp);
            temp=temp.next;
        }
        System.out.println(temp);
    }
}
